package com.sheng.leetcode.year2022.swordfingeroffer.day12;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/13
 *<p>
 * 剑指 Offer 25. 合并两个排序的链表<p>
 *<p>
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。<p>
 *<p>
 * 示例1：<p>
 *<p>
 * 输入：1->2->4, 1->3->4<p>
 * 输出：1->1->2->3->4->4<p>
 * 限制：<p>
 *<p>
 * 0 <= 链表长度 <= 1000<p>
 *<p>
 * 注意：本题与主站 21 题相同：<a href="https://leetcode-cn.com/problems/merge-two-sorted-lists/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接<a href="：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lco">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Sword0025 {

    @Test
    public void test01() {
        ListNode l1 = new ListNode(1);
        ListNode ll1 = new ListNode(2);
        ListNode lll1 = new ListNode(4);
        ll1.next = lll1;
        l1.next = ll1;
        ListNode l2 = new ListNode(1);
        ListNode ll2 = new ListNode(3);
        ListNode lll2 = new ListNode(4);
        ll2.next = lll2;
        l2.next = ll2;
        ListNode node = new Solution().mergeTwoLists(l1, l2);
        System.out.println(node);
    }
}
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        while (l1 != null) {
            list.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            list.add(l2.val);
            l2 = l2.next;
        }
        list.sort(Comparator.comparingInt(o -> o));
        ListNode node = new ListNode(list.get(0));
        ListNode pre = node;
        for (int i = 1; i < list.size(); i++) {
            pre.next = new ListNode(list.get(i));
            pre = pre.next;
        }
        return node;
    }
}

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

//class Solution {
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        ListNode dummy = new ListNode(-1), cur = dummy;
//        while (l1 != null || l2 != null) {
//            if (l1 != null && l2 != null) {
//                if (l1.val < l2.val) {
//                    cur.next = l1;
//                    cur = cur.next; l1 = l1.next;
//                } else {
//                    cur.next = l2;
//                    cur = cur.next; l2 = l2.next;
//                }
//            } else if (l1 != null) {
//                cur.next = l1;
//                cur = cur.next; l1 = l1.next;
//            } else {
//                cur.next = l2;
//                cur = cur.next; l2 = l2.next;
//            }
//        }
//        return dummy.next;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/solution/by-ac_oier-d6wf/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
